import { TreeNode } from "../../utils/treeUtil"

/**105. 从前序与中序遍历序列构造二叉树
 * - 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
export function buildTreeByPreIn(preorder: number[], inorder: number[]): TreeNode | null {
    //思路：以前序数组，确定中节点。
    // 在中序数组中找出该节点的位置，分割数组，左边是左子树，右边是右子树 （的中序遍历）
    // 在前序数组一样进行切割，虽然不知道前序数组要切割多少，但是 “前序和中序数组长度相等”， 所以可以判断出来要切出 1 ~ index+1  （从1开始是因为0被用了）
    if (preorder.length === 0) return null
    const root = new TreeNode(preorder[0])
    const index = inorder.indexOf(root.val)
    root.left = buildTreeByPreIn(preorder.slice(1, index + 1), inorder.slice(0, index))
    root.right = buildTreeByPreIn(preorder.slice(index + 1), inorder.slice(index + 1))
    return root
}
/**106. 从中序与后序遍历序列构造二叉树
 * - 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 */
export function buildTreeByPostIn(inorder: number[], postorder: number[]): TreeNode | null {
    // 后序数组，最后的是中节点。找到中节点，切割中序数组，左边就是左子树，右边就是右子树
    if (postorder.length === 0) return null
    const root = new TreeNode(postorder[postorder.length - 1])
    const index = inorder.indexOf(root.val)
    //切割的时候，一定要记得，切割出来的数组长度相等，用这条规则，就可以知道后序数组要切割多少了
    root.left = buildTreeByPostIn(inorder.slice(0, index), postorder.slice(0, index))
    root.right = buildTreeByPostIn(inorder.slice(index + 1), postorder.slice(index, - 1))
    return root
}